home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Libraries / KPlib 1.3.5 / KPArray.h next >
Text File  |  1995-12-17  |  16KB  |  619 lines
  1. // A module of KPLib v1.3.5.
  2. // Written by Keith Pomakis during the summer of 1994.
  3. // Released to the public domain on October 10, 1994.
  4.  
  5. #ifndef KP_ARRAY_DEFINED
  6. #define KP_ARRAY_DEFINED
  7.  
  8. #include <iostream.h>
  9. #include <stdlib.h>
  10. #include "KPbasic.h"
  11.  
  12. // Assumes Element has a default constructor and operator=().
  13.  
  14. template <class Element>
  15. class KPArray {
  16.     public:
  17.         KPArray();
  18.         KPArray(int size);
  19.         KPArray(int size, const Element &init_element);
  20.         KPArray(const KPArray<Element> &array);
  21.         virtual ~KPArray();
  22.         KPArray<Element> &operator=(const KPArray<Element> &array);
  23.         Element &operator[](int index);
  24.         const Element &operator[](int index) const;
  25.         int size() const;
  26.         bool is_empty() const;
  27.         void resize(int new_size);
  28.         void resize(int new_size, const Element &init_element);
  29.         void set_all_to(const Element &element);
  30.     protected:
  31.         static void error(const char *msg);
  32.         int my_size;
  33.         Element *my_elements;
  34. };
  35.  
  36. // Assumes Element has the above plus operator==().
  37.  
  38. template <class Element>
  39. class KPComparableArray: public KPArray<Element> {
  40.     public:
  41.         KPComparableArray();
  42.         KPComparableArray(int size);
  43.         KPComparableArray(int size, const Element &init_element);
  44.         KPComparableArray(const KPComparableArray<Element> &array);
  45.         KPComparableArray(const KPArray<Element> &array);
  46.         virtual ~KPComparableArray();
  47.         KPComparableArray<Element> &operator=(const KPArray<Element> &array);
  48.         bool operator==(const KPComparableArray<Element> &array) const;
  49.         bool operator!=(const KPComparableArray<Element> &array) const;
  50.         bool contains(const Element &element) const;
  51.         int occurrences_of(const Element &element) const;
  52.         int index_of(const Element &element) const;
  53.     protected:
  54.         static void error(const char *msg);
  55. };
  56.  
  57. // Assumes Element has the above plus operator<().  Note that this operator
  58. // must place a total ordering on the set of Elements.
  59.  
  60. template <class Element>
  61. class KPSortableArray: public KPComparableArray<Element> {
  62.     public:
  63.         KPSortableArray();
  64.         KPSortableArray(int size);
  65.         KPSortableArray(int size, const Element &init_element);
  66.         KPSortableArray(const KPSortableArray<Element> &array);
  67.         KPSortableArray(const KPArray<Element> &array);
  68.         virtual ~KPSortableArray();
  69.         KPSortableArray<Element> &operator=(const KPArray<Element> &array);
  70.         void sort();
  71.         Element &min();
  72.         const Element &min() const;
  73.         Element &max();
  74.         const Element &max() const;
  75.     protected:
  76.         static void error(const char *msg);
  77.         int findpivot(int i, int j);
  78.         int partition(int l, int r, const Element &pivot);
  79.         void quicksort(int i, int j);
  80. };
  81.  
  82. /****************************************************************************/
  83.  
  84. template <class Element>
  85. inline
  86. KPArray<Element>::KPArray(): my_size(0)
  87. {
  88.     /* do nothing */
  89. }
  90.  
  91. /****************************************************************************/
  92.  
  93. template <class Element>
  94. KPArray<Element>::KPArray(int size)
  95. {
  96.     if (size < 0)
  97.         error("KPArray() - size of KPArray must be non-negative");
  98.  
  99.     my_size = size;
  100.     my_elements = new Element[size];
  101.     check_mem(my_elements);
  102. }
  103.  
  104. /****************************************************************************/
  105.  
  106. template <class Element>
  107. KPArray<Element>::KPArray(int size, const Element &init_element)
  108. {
  109.     if (size < 0)
  110.         error("KPArray() - size of KPArray must be non-negative");
  111.  
  112.     my_size = size;
  113.     if (my_size > 0) {
  114.         my_elements = new Element[size];
  115.         check_mem(my_elements);
  116.         for (int i=0; i<size; i++)
  117.             my_elements[i] = init_element;
  118.     }
  119. }
  120.  
  121. /****************************************************************************/
  122.  
  123. template <class Element>
  124. KPArray<Element>::KPArray(const KPArray<Element> &array)
  125. {
  126.     my_size = array.my_size;
  127.     if (my_size > 0) {
  128.         my_elements = new Element[my_size];
  129.         check_mem(my_elements);
  130.         for (int i=0; i<my_size; i++)
  131.             my_elements[i] = array.my_elements[i];
  132.     }
  133. }
  134.  
  135. /****************************************************************************/
  136.  
  137. template <class Element>
  138. inline
  139. KPArray<Element>::~KPArray()
  140. {
  141.     if (my_size > 0)
  142.         delete [] my_elements;
  143. }
  144.  
  145. /****************************************************************************/
  146.  
  147. template <class Element>
  148. KPArray<Element> &
  149. KPArray<Element>::operator=(const KPArray<Element> &array)
  150. {
  151.     if (this == &array)
  152.         return *this;
  153.  
  154.     bool resize = (my_size != array.my_size);
  155.  
  156.     if (my_size > 0 && resize)
  157.         delete [] my_elements;
  158.  
  159.     my_size = array.my_size;
  160.     if (my_size > 0) {
  161.         if (resize) {
  162.             my_elements = new Element[my_size];
  163.             check_mem(my_elements);
  164.         }
  165.         for (int i=0; i<my_size; i++)
  166.             my_elements[i] = array.my_elements[i];
  167.     }
  168.     return *this;
  169. }
  170.  
  171. /****************************************************************************/
  172.  
  173. template <class Element>
  174. inline Element &
  175. KPArray<Element>::operator[](int index)
  176. {
  177.     if (index < 0 || index >= my_size)
  178.         error("operator[] - invalid index");
  179.  
  180.     return my_elements[index];
  181. }
  182.  
  183. /****************************************************************************/
  184.  
  185. template <class Element>
  186. inline const Element &
  187. KPArray<Element>::operator[](int index) const
  188. {
  189.     if (index < 0 || index >= my_size)
  190.         error("operator[] - invalid index");
  191.  
  192.     return my_elements[index];
  193. }
  194.  
  195. /****************************************************************************/
  196.  
  197. template <class Element>
  198. inline int
  199. KPArray<Element>::size() const
  200. {
  201.     return my_size;
  202. }
  203.  
  204. /****************************************************************************/
  205.  
  206. template <class Element>
  207. inline bool
  208. KPArray<Element>::is_empty() const
  209. {
  210.     return (my_size == 0);
  211. }
  212.  
  213. /****************************************************************************/
  214.  
  215. template <class Element>
  216. void
  217. KPArray<Element>::resize(int new_size)
  218. {
  219.     if (my_size == new_size)
  220.         return;
  221.  
  222.     if (new_size < 0)
  223.         error("resize() - size of KPArray must be non-negative");
  224.  
  225.     if (new_size > 0) {
  226.         Element *new_space = new Element[new_size];
  227.         check_mem(new_space);
  228.  
  229.         const int savable_elements = ::min(my_size, new_size);
  230.         for (int i=0; i<savable_elements; i++)
  231.             new_space[i] = my_elements[i];
  232.  
  233.         if (my_size > 0)
  234.             delete [] my_elements;
  235.         my_elements = new_space;
  236.     }
  237.     else
  238.         delete [] my_elements;
  239.  
  240.     my_size = new_size;
  241. }
  242.  
  243. /****************************************************************************/
  244.  
  245. template <class Element>
  246. void
  247. KPArray<Element>::resize(int new_size, const Element &init_element)
  248. {
  249.     if (my_size == new_size)
  250.         return;
  251.  
  252.     if (new_size < 0)
  253.         error("resize() - size of KPArray must be non-negative");
  254.  
  255.     if (new_size > 0) {
  256.         Element *new_space = new Element[new_size];
  257.         check_mem(new_space);
  258.  
  259.         int i;
  260.         const int savable_elements = ::min(my_size, new_size);
  261.         for (i=0; i<savable_elements; i++)
  262.             new_space[i] = my_elements[i];
  263.  
  264.         if (my_size > 0)
  265.             delete [] my_elements;
  266.         my_elements = new_space;
  267.  
  268.         for (i=my_size; i<new_size; i++)
  269.             my_elements[i] = init_element;
  270.     }
  271.     else
  272.         delete [] my_elements;
  273.  
  274.     my_size = new_size;
  275. }
  276.  
  277. /****************************************************************************/
  278.  
  279. template <class Element>
  280. void
  281. KPArray<Element>::set_all_to(const Element &element)
  282. {
  283.     for (int i=0; i<my_size; i++)
  284.         my_elements[i] = element;
  285. }
  286.  
  287. /****************************************************************************/
  288.  
  289. template <class Element>
  290. void
  291. KPArray<Element>::error(const char *msg)
  292. {
  293.     cerr << "KPArray: " << msg << '\n';
  294.     exit(EXIT_FAILURE);
  295. }
  296.  
  297. /****************************************************************************/
  298.  
  299. template <class Element>
  300. inline
  301. KPComparableArray<Element>::KPComparableArray(): KPArray<Element>()
  302. { /* do nothing new. */ }
  303.  
  304. /****************************************************************************/
  305.  
  306. template <class Element>
  307. inline
  308. KPComparableArray<Element>::KPComparableArray(int size): KPArray<Element>(size)
  309. { /* do nothing new. */ }
  310.  
  311. /****************************************************************************/
  312.  
  313. template <class Element>
  314. inline
  315. KPComparableArray<Element>::KPComparableArray(int size,
  316.             const Element &init_element): KPArray<Element>(size, init_element)
  317. { /* do nothing new. */ }
  318.  
  319. /****************************************************************************/
  320.  
  321. template <class Element>
  322. inline
  323. KPComparableArray<Element>::KPComparableArray(
  324.             const KPComparableArray<Element> &array): KPArray<Element>(array)
  325. { /* do nothing new. */ }
  326.  
  327. /****************************************************************************/
  328.  
  329. template <class Element>
  330. inline
  331. KPComparableArray<Element>::KPComparableArray(const KPArray<Element> &array):
  332.                                                 KPArray<Element>(array)
  333. { /* do nothing new. */ }
  334.  
  335. /****************************************************************************/
  336.  
  337. template <class Element>
  338. inline
  339. KPComparableArray<Element>::~KPComparableArray()
  340. { /* do nothing new. */ }
  341.  
  342. /****************************************************************************/
  343.  
  344. template <class Element>
  345. inline KPComparableArray<Element> &
  346. KPComparableArray<Element>::operator=(const KPArray<Element> &array)
  347. {
  348.     KPArray<Element>::operator=(array);
  349.     return *this;
  350. }
  351.  
  352. /****************************************************************************/
  353.  
  354. template <class Element>
  355. bool
  356. KPComparableArray<Element>::operator==(const KPComparableArray<Element> &array)
  357.                                                                         const
  358. {
  359.     if (this == &array)
  360.         return true;
  361.     
  362.     if (my_size != array.my_size)
  363.         return false;
  364.  
  365.     for (int i=0; i<my_size; i++)
  366.         if (!(my_elements[i] == array.my_elements[i]))
  367.             return false;
  368.     
  369.     return true;
  370. }
  371.  
  372. /****************************************************************************/
  373.  
  374. template <class Element>
  375. inline bool
  376. KPComparableArray<Element>::operator!=(const KPComparableArray<Element> &array)
  377.                                                                         const
  378. {
  379.     return !(*this == array);
  380. }
  381.  
  382. /****************************************************************************/
  383.  
  384. template <class Element>
  385. inline bool
  386. KPComparableArray<Element>::contains(const Element &element) const
  387. {
  388.     return (index_of(element) != -1);
  389. }
  390.  
  391. /****************************************************************************/
  392.  
  393. template <class Element>
  394. int
  395. KPComparableArray<Element>::occurrences_of(const Element &element) const
  396. {
  397.     int occurrences = 0;
  398.  
  399.     for (int i=0; i<my_size; i++)
  400.         if (my_elements[i] == element)
  401.             occurrences++;
  402.  
  403.     return occurrences;
  404. }
  405.  
  406. /****************************************************************************/
  407.  
  408. template <class Element>
  409. int
  410. KPComparableArray<Element>::index_of(const Element &element) const
  411. {
  412.     for (int i=0; i<my_size; i++)
  413.         if (my_elements[i] == element)
  414.             return i;
  415.  
  416.     return -1;
  417. }
  418.  
  419. /****************************************************************************/
  420.  
  421. template <class Element>
  422. void
  423. KPComparableArray<Element>::error(const char *msg)
  424. {
  425.     cerr << "KPComparableArray: " << msg << '\n';
  426.     exit(EXIT_FAILURE);
  427. }
  428.  
  429. /****************************************************************************/
  430.  
  431. template <class Element>
  432. inline
  433. KPSortableArray<Element>::KPSortableArray(): KPComparableArray<Element>()
  434. { /* do nothing new. */ }
  435.  
  436. /****************************************************************************/
  437.  
  438. template <class Element>
  439. inline
  440. KPSortableArray<Element>::KPSortableArray(int size):
  441.                                             KPComparableArray<Element>(size)
  442. { /* do nothing new. */ }
  443.  
  444. /****************************************************************************/
  445.  
  446. template <class Element>
  447. inline
  448. KPSortableArray<Element>::KPSortableArray(int size,
  449.     const Element &init_element): KPComparableArray<Element>(size, init_element)
  450. { /* do nothing new. */ }
  451.  
  452. /****************************************************************************/
  453.  
  454. template <class Element>
  455. inline
  456. KPSortableArray<Element>::KPSortableArray(const KPSortableArray<Element>
  457.                                     &array): KPComparableArray<Element>(array)
  458. { /* do nothing new. */ }
  459.  
  460. /****************************************************************************/
  461.  
  462. template <class Element>
  463. inline
  464. KPSortableArray<Element>::KPSortableArray(const KPArray<Element> &array):
  465.                                             KPComparableArray<Element>(array)
  466. { /* do nothing new. */ }
  467.  
  468. /****************************************************************************/
  469.  
  470. template <class Element>
  471. inline
  472. KPSortableArray<Element>::~KPSortableArray()
  473. { /* do nothing new. */ }
  474.  
  475. /****************************************************************************/
  476.  
  477. template <class Element>
  478. inline KPSortableArray<Element> &
  479. KPSortableArray<Element>::operator=(const KPArray<Element> &array)
  480. {
  481.     KPComparableArray<Element>::operator=(array);
  482.     return *this;
  483. }
  484.  
  485. /****************************************************************************/
  486.  
  487. template <class Element>
  488. int
  489. KPSortableArray<Element>::findpivot(int i, int j)
  490. {
  491.     const Element &first = my_elements[i];
  492.     for (int k=i+1; k<=j; k++) {
  493.         if (first < my_elements[k])
  494.             return k;
  495.         else if (my_elements[k] < first)
  496.             return i;
  497.     }
  498.     return -1;
  499. }
  500.  
  501. template <class Element>
  502. int
  503. KPSortableArray<Element>::partition(int l, int r, const Element &pivot)
  504. {
  505.     do {
  506.         swap(my_elements[l], my_elements[r]);
  507.         while (my_elements[l] < pivot)
  508.             l++;
  509.         while (!(my_elements[r] < pivot))
  510.             r--;
  511.     } while (l <= r);
  512.     return l;
  513. }
  514.  
  515. template <class Element>
  516. void
  517. KPSortableArray<Element>::quicksort(int i, int j)
  518. {
  519.     Element pivot;
  520.     int k, index;
  521.  
  522.     index = findpivot(i, j);
  523.     if (index != -1) {
  524.         pivot = my_elements[index];
  525.         k = partition(i, j, pivot);
  526.         quicksort(i, k-1);
  527.         quicksort(k, j);
  528.     }
  529. }
  530.  
  531. template <class Element>
  532. inline void
  533. KPSortableArray<Element>::sort()
  534. {
  535.     quicksort(0, my_size-1);
  536. }
  537.  
  538. /****************************************************************************/
  539.  
  540. template <class Element>
  541. Element &
  542. KPSortableArray<Element>::min()
  543. {
  544.     if (my_size < 1)
  545.         error("min() - empty array");
  546.  
  547.     int min_index = 0;
  548.     for (int i=1; i<my_size; i++)
  549.         if (my_elements[i] < my_elements[min_index])
  550.             min_index = i;
  551.  
  552.     return my_elements[min_index];
  553. }
  554.  
  555. /****************************************************************************/
  556.  
  557. template <class Element>
  558. const Element &
  559. KPSortableArray<Element>::min() const
  560. {
  561.     if (my_size < 1)
  562.         error("min() - empty array");
  563.  
  564.     int min_index = 0;
  565.     for (int i=1; i<my_size; i++)
  566.         if (my_elements[i] < my_elements[min_index])
  567.             min_index = i;
  568.  
  569.     return my_elements[min_index];
  570. }
  571.  
  572. /****************************************************************************/
  573.  
  574. template <class Element>
  575. Element &
  576. KPSortableArray<Element>::max()
  577. {
  578.     if (my_size < 1)
  579.         error("max() - empty array");
  580.  
  581.     int max_index = 0;
  582.     for (int i=1; i<my_size; i++)
  583.         if (my_elements[max_index] < my_elements[i])
  584.             max_index = i;
  585.  
  586.     return my_elements[max_index];
  587. }
  588.  
  589. /****************************************************************************/
  590.  
  591. template <class Element>
  592. const Element &
  593. KPSortableArray<Element>::max() const
  594. {
  595.     if (my_size < 1)
  596.         error("max() - empty array");
  597.  
  598.     int max_index = 0;
  599.     for (int i=1; i<my_size; i++)
  600.         if (my_elements[max_index] < my_elements[i])
  601.             max_index = i;
  602.  
  603.     return my_elements[max_index];
  604. }
  605.  
  606. /****************************************************************************/
  607.  
  608. template <class Element>
  609. void
  610. KPSortableArray<Element>::error(const char *msg)
  611. {
  612.     cerr << "KPSortableArray: " << msg << '\n';
  613.     exit(EXIT_FAILURE);
  614. }
  615.  
  616. /****************************************************************************/
  617.  
  618. #endif /* KP_ARRAY_DEFINED */
  619.